public class Leetcode {
}

//leetcode:733:图像渲染
class Solution1 {
    int tmp = 0;
    int[] dx = {0,0,1,-1};
    int[] dy = {1,-1,0,0};
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        //如果此时位置的元素不为color就将他和周围的值改为color
        if(image[sr][sc] != color){
            tmp = image[sr][sc];
            dfs(image,sr,sc,color);
        }
        return image;
    }
     public void dfs(int[][] image,int i, int j, int color){
        image[i][j] = color;
        for(int k = 0; k < 4;k++){
            int x = i + dx[k],y = j + dy[k];
            if(x >= 0 && x < image.length && y>= 0 && y < image[0].length && image[x][y] == tmp){
                dfs(image,x,y,color);
            }
        }
     }
}

//leetcode:200:岛屿数量
class Solution2 {
    boolean[][] visits;
    int[] dx = {0,0,1,-1};
    int[] dy = {1,-1,0,0};
    int m , n;
    public int numIslands(char[][] grid) {
       m = grid.length;
       n = grid[0].length;
       int count = 0;
       visits = new boolean[m][n];
       for(int i = 0; i < m;i++){
        for(int j = 0; j < n;j++){
            //得到岛屿的数量
            if(!visits[i][j] && grid[i][j] == '1'){
                count++;
                dfs(grid,i,j);
            }
        }
       }
       return count;
    }
    //得到此时这个岛屿周围的所有岛屿，并将他们看成一个整体，即将这个岛屿和周围的岛屿都置为true
    public void dfs(char[][] grid,int i,int j){
        visits[i][j] = true;
        for(int k = 0; k < 4; k++){
            int x = i + dx[k],y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && !visits[x][y] && grid[x][y] == '1'){
                dfs(grid,x,y);
            }
        }
    }
}

//leetcode:695:岛屿的最大面积
class Solution3 {
    int[] dx = {0,0,1,-1};
    int[] dy = {1,-1,0,0};
    int m ,n,count;
    boolean[][] vistis;
    public int maxAreaOfIsland(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        int ret = 0;
        vistis = new boolean[m][n];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(!vistis[i][j] && grid[i][j] == 1){
                    count = 0;
                    dfs(grid,i,j);
                    //返回组成整体岛屿数量最大的
                    ret = Math.max(ret,count);
                }
            }
        }
        return ret;
    }
    //同上面一样在将岛屿看成整体的同时得到这个整体岛屿由多少的岛屿组成
    public int dfs(int[][] grid,int i, int j){
        count++;
        vistis[i][j] = true;
        for(int k = 0; k < 4;k++){
            int x = i + dx[k],y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && !vistis[x][y] && grid[x][y] == 1){
                dfs(grid,x,y);
            }
        }
        return count;
    }
}

//leetcode:130:被围绕的区域
//遇难则反
//将边界的‘O’都转换为‘.’,然后再遍历整个数组将'.'转变为'O',将'O'转变为‘X’
class Solution {
    int m,n;
    int[] dx = {0,0,1,-1};
    int[] dy = {1,-1,0,0};
    public void solve(char[][] board) {
        m = board.length;
        if(m == 0){
            return;
        }
        n = board[0].length;
        for(int i = 0; i < m; i++){
            dfs(board,i,0);
            dfs(board,i,n-1);
        }
        for(int i = 1; i < n-1;i++){
            dfs(board,0,i);
            dfs(board,m-1,i);
        }
        for(int i = 0; i < m;i++){
            for(int j = 0; j < n;j++){
                if(board[i][j] == 'O'){
                    board[i][j] = 'X';
                }else if(board[i][j] == '.'){
                   board[i][j] = 'O';
                }
            }
        }
    }

    public void dfs(char[][] board,int i ,int j){
        if(board[i][j] == 'O'){
            board[i][j] = '.';
           for(int k = 0; k < 4;k++){
            int x = i + dx[k],y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O'){
                dfs(board,x,y);
            }
          }
        }
    }
}